package LeetCode;

import java.util.ArrayList;

/**
 * Working!!!!!
 *
 */
public class NQueens {
  
  /* Check if (row1, column1) is a valid spot for a queen by checking if there
   * is a queen in the same column or diagonal. We don't need to check it for queens
   * in the same row because the calling placeQueen only attempts to place one queen at
   * a time. We know this row is empty. 
   */
  public static boolean checkValid(Integer[] columns, int row1, int column1) {
      for (int row2 = 0; row2 < row1; row2++) {
          int column2 = columns[row2];
          /* Check if (row2, column2) invalidates (row1, column1) as a queen spot. */
          
          /* Check if rows have a queen in the same column */
          if (column1 == column2) { 
              return false;
          }
          
          /* Check diagonals: if the distance between the columns equals the distance
           * between the rows, then they're in the same diagonal.
           */
          int columnDistance = Math.abs(column2 - column1); 
          int rowDistance = row1 - row2; // row1 > row2, so no need to use absolute value
          if (columnDistance == rowDistance) {
              return false;
          }
      }
      return true;
  }
  
  public static void placeQueens(int row, Integer[] columns, ArrayList<Integer[]> results, int GRID_SIZE) {
      if (row == GRID_SIZE) { // Found valid placement
          results.add(columns.clone()); 
      } else {
          for (int col = 0; col < GRID_SIZE; col++) {         
              if (checkValid(columns, row, col)) {
                  columns[row] = col; // Place queen
                  placeQueens(row + 1, columns, results, GRID_SIZE); 
              }       
          }
      }
  }
  
  public static void clear(Integer[] columns, int GRID_SIZE) {
      for (int i = 0; i < GRID_SIZE; i++) {
          columns[i] = -1;
      }
  }
  
  public static String[] printBoard(Integer[] columns, int GRID_SIZE) {
    String[] result = new String[GRID_SIZE];
      //System.out.println("-----------------");
      for(int i = 0; i < GRID_SIZE; i++){
          //System.out.print("|");
          String columnStr = "";
          for (int j = 0; j < GRID_SIZE; j++){
              if (columns[i] == j) {
                  //System.out.print("Q|");
                  columnStr+="Q";
              } else {
                  //System.out.print(" |");
                  columnStr+=".";
              }
          }
          result[i] = columnStr;
          //System.out.println("\n-----------------");
      }
      //System.out.println("");
      return result;
  }

  
  public static ArrayList<String[]> printBoards(ArrayList<Integer[]> boards, int n) {
    ArrayList<String[]> result = new ArrayList<String[]>();
      for (int i = 0; i < boards.size(); i++) {
          Integer[] board = boards.get(i);
          result.add(printBoard(board, n));
      }
      return result;
  }
  
  public ArrayList<String[]> solveNQueens(int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<Integer[]> results = new ArrayList<Integer[]>();
    Integer[] columns = new Integer[n];
    clear(columns, n);
    placeQueens(0, columns, results, n);
    return printBoards(results, n);
  }
  
  public int totalNQueens(int n) {
    // Start typing your Java solution below
    // DO NOT write main() function
    ArrayList<Integer[]> results = new ArrayList<Integer[]>();
    Integer[] columns = new Integer[n];
    clear(columns, n);
    placeQueens(0, columns, results, n);
    return results.size();
  }
     
  public static void main(String[] args) {
    NQueens q = new NQueens();
    q.solveNQueens(8);
  }
}
